package com.yangzhe.algorithm.c037;

// 搜索二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
public class Code02_LowestCommonAncestorBinarySearch_LeetCode {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    /**
     * BST任何节点的值，左边都小于这个值，右边都大于这个值
     * 思路：
     * 1. 如果root.val < p.val && root.val < q.val，则代表LCA在右树
     * 2. 如果root.val > p.val && root.val > q.val，则代表LCA在左树
     * 3. 如果root.val <= p/q.val && root.val >= q/q.val，则代表LCA就是root
     * <p>
     * 在BST上寻找LCA是可以比经典方法优化，时间复杂度可比普通算法优化到 O(H)。
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            // root比q和p都小，则在右树
            if (root.val < p.val && root.val < q.val) {
                root = root.right;
            }

            // root比q和p都大，则在左树
            if (root.val > p.val && root.val > q.val) {
                root = root.left;
            }

            TreeNode small = p.val < q.val ? p : q;
            TreeNode big = small == p ? q : p;
            // 如果root在p和q之间，则root一定是LCA
            if (root.val >= small.val && root.val <= big.val) {
                return root;
            }
        }

        return null;
    }

}
